using System;
using System.Collections.Generic;
using System.Text;
using MathNet.Numerics.LinearAlgebra;
using System.Globalization;

namespace igather.Framework
{
    //TODO: [diogoriba] Handle error conditions in the edge methods better
    /// <summary>
    /// An implementation of a graph using a matrix
    /// </summary>
    public class UndirectedMatrixGraph : IGraph
    {
		private Matrix mMatrix;

        internal Matrix Matrix
        {
            get { return mMatrix; }
        }

        private List<Vertex> mVertices;

		private const int DEFAULT_MATRIX_SIZE = 1;
		
		/// <summary>
		/// Default constructor 
		/// </summary>
		public UndirectedMatrixGraph()
		{
			mMatrix = new Matrix(DEFAULT_MATRIX_SIZE, DEFAULT_MATRIX_SIZE);
			mVertices = new List<Vertex>();
		}
		
        /// <summary>
        /// Parametrized constructor
        /// </summary>
        /// <param name="size">The number of vertices in this graph</param>
        public UndirectedMatrixGraph(int size, List<Vertex> vertices)
        {
            mMatrix = new Matrix(size, size);
            mVertices = vertices;
        }

        #region IGraph Members

        /// <summary>
        /// Adds a vertex to this graph
        /// </summary>
        /// <param name="v">Vertex to add</param>
        public void AddVertex(Vertex v)
        {
            Matrix oldMatrix = mMatrix;
			mMatrix = new Matrix(oldMatrix.RowCount + 1, oldMatrix.ColumnCount + 1);
			
			for (int i = 0; i < oldMatrix.RowCount; i++)
				for (int j = 0; j < oldMatrix.ColumnCount; j++)
					mMatrix[i, j] = oldMatrix[i, j];
			
			mVertices.Add(v);
        }

        /// <summary>
        /// Finds a vertex in the graph
        /// </summary>
        /// <param name="v">Vertex to find</param>
        /// <returns>The vertex if it is found, otherwise false</returns>
        public Vertex GetVertex(Vertex v)
        {
            int index = mVertices.IndexOf(v);
			Vertex found = null;
            if (index > mVertices.Count)
                throw new IndexOutOfRangeException("There has been a problem while trying to retrieve this vertex");
			if (index >= 0)
				found = mVertices[index];

            return found;
        }

        /// <summary>
        /// Removes a vertex from the graph
        /// </summary>
        /// <param name="v">Vertex to remove</param>
        /// <returns>True if vertex was removed, otherwise false</returns>
        public bool RemoveVertex(Vertex v)
        {
            int index = mVertices.IndexOf(v);
			Matrix oldMatrix = mMatrix;
			
			//Handle error conditions
			if ((oldMatrix.RowCount <= 1) || (oldMatrix.ColumnCount <= 1))
				throw new InvalidOperationException("Cannot remove vertex from a graph with only one vertex");
			
			//Update dictionary
			mVertices.Remove(v);
			
			//Create a new matrix without the line/column for the deleted vertex
			mMatrix = new Matrix(oldMatrix.RowCount - 1, oldMatrix.ColumnCount - 1);
			int newRow = 0;
			int newColumn = 0;
			for (int row = 0; row < oldMatrix.RowCount; row++)
			{
				if (row != index)
				{
					newColumn = 0;
					for (int column = 0; column < oldMatrix.ColumnCount; column++)
					{
						if (column != index)
						{
							mMatrix[newRow, newColumn] = oldMatrix[row, column];
							newColumn++;
						}
					}
					newRow++;
				}
			}
			
			return true;
        }

        /// <summary>
        /// Gets the list of edges for a vertex
        /// </summary>
        /// <param name="v">Vertex to get the edges from</param>
        /// <returns>The list of edges for a vertex</returns>
        public List<Edge> GetEdges(Vertex v)
        {
            List<Edge> edges = new List<Edge>();
            int row = mVertices.IndexOf(v);
            if ((row < 0) || (row > mVertices.Count))
                throw new IndexOutOfRangeException("There has been a problem while trying to retrieve the edges of this vertex");

            for (int column = 0; column < mMatrix.ColumnCount; column++)
            {
                if (mMatrix[row, column] > 0)
                {
                    Edge edge = new Edge(IsDirected, mVertices[row], mVertices[column], mMatrix[row, column]);
                    edges.Add(edge);
                }
            }

            return edges;
        }

        /// <summary>
        /// Gets the list of vertices in this graph
        /// </summary>
        public List<Vertex> Vertices
        {
            get { return mVertices; }
        }

        /// <summary>
        /// True if this graph is directed, otherwise false
        /// </summary>
        public bool IsDirected
        {
            get { return false; }
        }

        /// <summary>
        /// Creates a new edge from this graph
        /// </summary>
        /// <param name="head">Head vertex for this edge</param>
        /// <param name="tail">Tail vertex for this edge</param>
        /// <returns>An instance of the Edge class</returns>
        public Edge CreateEdge(Vertex head, Vertex tail)
        {
            return CreateEdge(head, tail, 0);
        }

        /// <summary>
        /// Creates a new edge from this graph
        /// </summary>
        /// <param name="head">Head vertex for this edge</param>
        /// <param name="tail">Tail vertex for this edge</param>
        /// <returns>An instance of the Edge class</returns>
        public Edge CreateEdge(Vertex head, Vertex tail, double weight)
        {
            return new Edge(IsDirected, head, tail, weight);
        }

        /// <summary>
        /// Adds an edge to this graph
        /// </summary>
        /// <param name="e">Edge to add</param>
        public void AddEdge(Edge e)
        {
            int headIndex = mVertices.IndexOf(e.Head);
            int tailIndex = mVertices.IndexOf(e.Tail);
			
			//if ((mMatrix[headIndex, tailIndex] > 0) || (mMatrix[tailIndex, headIndex] > 0))
			//	throw new ArgumentException("Cannot add duplicate edge");
			
            mMatrix[headIndex, tailIndex] = e.Weight;
            mMatrix[tailIndex, headIndex] = e.Weight;
        }

        /// <summary>
        /// Finds an edge in this graph
        /// </summary>
        /// <param name="e">Edge to find</param>
        /// <returns>The edge if it is found, otherwise null</returns>
        public Edge GetEdge(Edge e)
        {
            int headIndex = mVertices.IndexOf(e.Head);
            int tailIndex = mVertices.IndexOf(e.Tail);

            Edge edge = null;
            double weight = mMatrix[headIndex, tailIndex];
            if (weight > 0)
            {
                edge = new Edge(IsDirected, e.Head, e.Tail, weight);
            }

            return edge;
        }

        /// <summary>
        /// Removes an edge from the graph
        /// </summary>
        /// <param name="e">Edge to remove</param>
        /// <returns>True if edge was removed, otherwise false</returns>
        public bool RemoveEdge(Edge e)
        {
            int headIndex = mVertices.IndexOf(e.Head);
            int tailIndex = mVertices.IndexOf(e.Tail);

            bool removed = false;

            if ((mMatrix[headIndex, tailIndex] > 0) && (mMatrix[headIndex, tailIndex] == mMatrix[tailIndex, headIndex]))
            {
                mMatrix[headIndex, tailIndex] = 0;
                mMatrix[tailIndex, headIndex] = 0;
                removed = true;
            }

            return removed;
        }

        /// <summary>
        /// Gets the list of edges with at least one node in this graph
        /// </summary>
        public List<Edge> Edges
        {
            get 
            {
                List<Edge> edges = new List<Edge>();
                for (int i = 0; i < mMatrix.RowCount; i++)
                {
                    for (int j = 0; j < mMatrix.ColumnCount; i++)
                    {
                        if (mMatrix[i, j] > 0)
                        {
                            Edge e = new Edge(IsDirected, mVertices[i], mVertices[j], mMatrix[i, j]);
                            edges.Add(e);
                        }
                    }
                }

                return edges;
            }
        }
		
		/// <summary>
		/// Create a matrix that represents this graph 
		/// </summary>
		/// <returns>
		/// A matrix representation of this graph
		/// </returns>
		public Matrix ToMatrix()
		{
			Matrix result = Matrix;

            return result;
		}
		
		/// <summary>
		/// Creates a string representation of this graph 
		/// </summary>
		/// <remarks>
		/// The format used here is GraphViz's
		/// http://www.graphviz.org/
		/// </remarks>
		/// <returns>
		/// A string repreentation of this graph
		/// </returns>
		public override string ToString()
		{
            StringBuilder returnString = new StringBuilder();
            returnString.AppendLine("graph G {");

			foreach (Edge e in Edges)
				if (e.Weight != 0)
					returnString.AppendLine(string.Format("\"{0}\" -- \"{1}\" [label={2}]", e.Head.Name, e.Tail.Name, e.Weight));
			
            returnString.AppendLine("}");
            return returnString.ToString();
		}

        #endregion
    }
}
